package org.myy.learn.hot.多维动态规划;

import lombok.extern.slf4j.Slf4j;

/**
 * 力扣64
 */
@Slf4j
public class 最小路径和 {
    public static int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        if (m==0 && n==0){return 0;}
        //动态变量
        int[][] dp = new int[m][n];
        //初始化
        dp[0][0] = grid[0][0];
        for (int i=1; i<m; i++){
            dp[i][0] = dp[i-1][0]+grid[i][0];
        }
        for (int j=1; j<n; j++){
            dp[0][j] = dp[0][j-1]+grid[0][j];
        }
        for (int i=1; i<m; i++){
            for (int j=1; j<n; j++){
                dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1])+grid[i][j];
            }
        }
        return dp[m-1][n-1];
    }

    public static void main(String[] args) {
        //[[1,3,1],[1,5,1],[4,2,1]]
        int[][] grid = new int[][]{{1,2,3},{4,5,6}};
        int minPathSum = minPathSum(grid);
        log.info("执行结束，minPathSum={}",minPathSum);
    }
}
